【题解】 「网络流24题」最长不下降子序列问题 网络流 luoguP2766 | Qiuly's blog!

【题解】 「网络流24题」最长不下降子序列问题 网络流 luoguP2766

Posted on | Edited on | In | Comments:

第一问显然是一个很简单的 $DP$ ，但是第二问和第三问就要用最大流来求了，怎么求呢？

首先我们 $DP$ 出来的 $f$ 数组，$f[i]$ 表示以i结尾的最长不下降子序列的长度 ，然后就是网络流的连边了。首先因为一个点只能经过两次，我们需要将其拆为入点和出点，中间连的边的边权自然是 $1$ ，然后对于一个 $i$ ，如果 $f[i]$ 等于最长长度($s$)，那么很显然这个 $i$ 就可以给答案做出一个贡献，这个时候 $i$ 的出点向 $t$ 连一条边权为 $1$ 边。

如果 $i$ 等于 $1$ ，那么自然 $1$ 是可以作为一个起点的，那么 $s$ 向 $i$ 的入点连一条边权为 $1$ 的边即可。

然后就是剩下的情况了，可以想到让 $i$ 向 $i$ 能够最优转移的位置连边，也就是说，如果有一个 $j$ ，使得 $f[j]=f[i]+1$ 并且 $a[i]<=a[j]$ ，这个时候如果是在最优方案中 $i$ 是可以转移到 $j$ 的，这个时候从 $i$ 的出点向 $j$ 的入点连一条边，边权依旧是 $1$ 。

然后我们这个时候跑最大流，就是第二问的答案。

那么第三问呢？

很显然，对于 $1$ ，如果它是连向 $s$ 的，则将其连向 $s$ 的边的边权改为 $inf$ ，并将入点连出点的边权改为 $inf$ ，表示可以取无限次。然后 $n$ 如果连向了 $t$ ，也将边权改为 $inf$ ，并将入点连出点的边权改为 $inf$ ，和上面同理。这个时候再跑一次最大流即可，这就是第三问的答案了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e5+7;
const int M=5e2+7;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

namespace Dinic {
    queue<int> q;
    int s,t,head[N],cnt=1,dep[N];
    struct Edge {int nxt,to,val;}G[N];
    inline void add(int u,int v,int w) {
        G[++cnt]={head[u],v,w},head[u]=cnt;
        G[++cnt]={head[v],u,0},head[v]=cnt;
    } 
    inline int bfs() {
        memset(dep,0,sizeof(dep));
        dep[s]=1,q.push(s);
        while(!q.empty()) {
            int u=q.front(),v;q.pop();
            for(int i=head[u];i;i=G[i].nxt)
                if(!dep[v=G[i].to]&&G[i].val>0)
                    dep[v]=dep[u]+1,q.push(v);
        }return dep[t];
    }
    int dfs(int u,int flow) {
        if(!flow||u==t) return flow;
        int used=0,rlow,v;
        for(int i=head[u];i;i=G[i].nxt)
            if(dep[v=G[i].to]==dep[u]+1&&G[i].val>0) {
                used+=(rlow=dfs(v,min(G[i].val,flow-used)));
                G[i].val-=rlow,G[i^1].val+=rlow;
            }
        if(!used) dep[u]=-1;
        return used;
    }
    inline int dinic() {
        int maxflow=0;
        while(bfs()) maxflow+=dfs(s,inf);
        return maxflow;
    }
}
using namespace Dinic;
int n,l,ans,a[N],f[N];
inline int id(int type,int x) {
    return type*n+x;
}
int main() {
    IN(n);s=0,t=2*n+1;
    for(int i=1;i<=n;++i) {
        IN(a[i]);
        for(int j=0;j<i;++j)
            if(a[j]<=a[i]) f[i]=max(f[i],f[j]+1);
        l=max(l,f[i]);
    }
    printf("%d\n",l);/*Q1*/
    for(int i=1;i<=n;++i) {
        add(id(0,i),id(1,i),1);
        if(f[i]==1) add(s,id(0,i),1);
        if(f[i]==l) add(id(1,i),t,1);
        for(int j=1;j<i;++j) 
            if(a[j]<=a[i]&&f[i]==f[j]+1)add(id(1,j),id(0,i),1);
    }
    ans=dinic();
    printf("%d\n",ans);/*Q2*/
    if(f[1]==1)add(s,id(0,1),inf),add(id(0,1),id(1,1),inf);
    if(f[n]==l)add(id(1,n),t,inf),add(id(0,n),id(1,n),inf);
    ans+=dinic();
    printf("%d\n",ans);/*Q3*/
    return 0;
}

本文标题:【题解】 「网络流24题」最长不下降子序列问题 网络流 luoguP2766

文章作者:Qiuly

发布时间:2019年03月26日 - 00:00

最后更新:2019年03月29日 - 13:54

原始链接:http://qiulyblog.github.io/2019/03/26/[题解]luoguP2766/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。